import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String str = in.nextLine();
            TreeNode root = creatTree(str);
            inOrder(root);
        }
    }
    public static int i = 0;
    public static TreeNode creatTree(String str){
        //首先那你要了解：“前序遍历”是什么
        TreeNode root = null;
        if (str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);
        }else {
            i++;
        }
        return root;
    }
    public static void inOrder(TreeNode root){
        if (root == null){
            return ;
        }else {
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
            System.out.println(root.right + " ");
        }
    }
    //最近的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root == null){
            return null;
        }
        if (root == p||root == q){
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if (leftRet != null && rightRet != null){//说明这两个节点分别在左右子树上
            return root;
        }else if (leftRet != null){//说明这两个节点都在左树上
            return leftRet;
        }else if (rightRet != null){//说明这两个节点都在右树上
            return rightRet;
        }
        return null;
    }
    //另一种方法
    public boolean getPath(TreeNode root, TreeNode node,
                           Deque<TreeNode> stack) {
        //（一棵树，指定的节点，所放至的栈）
        if(root == null || node == null){
            return false;
        }
        stack.push(root);
        //放完之后 要检查:root是否为要寻找的节点
        if(root == node) {
            return true;
        }
        //去左边找
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1) {
            return true;
        }
        //去右边找
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) {
            return true;
        }
        //如果一个路径一直到尽头还没有发现相应节点，说明路径错误，弹出节点
        stack.pop();
        return false;
    }
    //对栈进行操作
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        //1、两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2、判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int size = size1-size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            int size = size2-size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }
        //栈里面数据的个数 是一样的
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            //对栈中的元素进行判断，直到找到相同的元素为止
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }

    public String tree2str(TreeNode root) {
        if(root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChilde(root,stringBuilder);

        return stringBuilder.toString();
    }

    public void tree2strChilde(TreeNode t,StringBuilder stringBuilder) {
        if(t == null) {
            return;
        }
        stringBuilder.append(t.val);

        if(t.left != null) {
            stringBuilder.append("(");
            tree2strChilde(t.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            //左边为空了
            if(t.right != null) {
                //右边不为空
                stringBuilder.append("()");//左边为空右边不为空的情况
            }else {
                //右边为空
                return ;
            }
        }

        if(t.right == null) {
            return;
        }else {
            stringBuilder.append("(");
            tree2strChilde(t.right,stringBuilder);
            stringBuilder.append(")");
        }

    }
}
